package com.ljy.algorithm;

import java.util.*;

public class ZhuCiBiJin {
  public static void main(String[] args) {
    int _ = Integer.MAX_VALUE;
    MZ mz = new MZ();
    int[][] data =
        new int[][] {
          {0, 2, 8, 1, _, _, _, _, _, _, _},
          {_, 0, 6, _, 1, _, _, _, _, _, _},
          {_, _, 0, -7, _, _, _, _, _, _, _},
          {_, _, _, 0, _, _, 9, _, _, _, _},
          {_, _, 5, _, 0, _, _, _, 1, _, _},
          {_, _, -1, _, 3, 0, 4, _, _, _, _},
          {_, _, 2, _, _, _, 0, _, -3, 1, _,},
          {_, _, _, _, 2, _, _, 0, _, _, 9, _},
          {_, _, _, _, _, 6, _, 7, 0, _, _},
          {_, _, _, _, _, _, _, 1, _, 0, 4},
          {_, _, _, _, _, _, _, _, 2, _, 0}
        };
    mz.main(data);
  }
}

class MZ {
  int max = Integer.MAX_VALUE;
  int[][] data;
  int[] p1; // p1，p2用作存p(k)和p(k+1)
  int[] p2;
  int[][] d; // 用于存储每一次计算p的过程

  public void main(int[][] data) {
    int len = data.length;
    this.data = data;
    p1 = new int[len];
    p2 = new int[len];
    // p1赋初值
    for (int j = 0; j < len; j++) {
      p1[j] = data[0][j];
    }
    int t = 1;
    System.out.println("第" + t + "次");
    print(p1);
    while (true) {
      if (t++ > 20) {
        break;
      }
      // 由p1算p2
      d = getD(p1);
      // d的第i行最小的数字就是新的p2
      p2 = minInRow(d);
      System.out.println("\n第" + t + "次");
      System.out.println("p(1j)组成的矩阵(_表无穷):");
      print(d);
      System.out.println("P(1j):");
      print(p2);
      // 判读p1和p2是否相同
      if (Arrays.equals(p1, p2)) {
        System.out.println("最终结果");
        print(p2);
        break;
      } else {
        p1 = p2;
      }
    }
  }

  void print(int[][] a) {
    int len = a.length;
    for (int i = 0; i < len; i++) {
      System.out.print("p(1,"+(1+i)+") \t");
      for (int j = 0; j < len; j++) {
        if (a[i][j] == max) {
          System.out.print("_  ");
        } else {
          System.out.print(a[i][j] + "  ");
        }
      }
      System.out.println();
    }
  }

  void print(int[] a) {
    int len = a.length;
    for (int i = 0; i < len; i++) {
      if (a[i] == max) {
        System.out.print("_  ");
      } else {
        System.out.print(a[i] + "  ");
      }
    }
    System.out.println();
  }
  // 求每一行最小的数字
  int[] minInRow(int[][] d) {
    int len = d.length;
    int[] ans = new int[len];
    // 求每一行最小值
    int min;
    for (int i = 0; i < len; i++) {
      min = max;
      for (int j = 0; j < len; j++) {
        if (d[i][j] != max) {
          min = Math.min(min, d[i][j]);
        }
      }
      ans[i] = min;
    }
    return ans;
  }
  // 根据p1，得到的结果
  int[][] getD(int[] p1) {
    int len = p1.length;
    int[][] ans = new int[len][len];
    for (int i = 0; i < len; i++) {
      for (int j = 0; j < len; j++) {
        if (p1[i] == max || data[i][j] == max) {
          ans[j][i] = max;
        } else {
          ans[j][i] = p1[i] + data[i][j];
        }
      }
    }
    return ans;
  }
}
